#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;


//method 1
vector<Tree *> genSibling(Tree *root)
{
    Tree dummy(0); 
    Tree *cur = &dummy;
    vector<Tree *> ans;
    if (!root) return ans;
    root->sibling = NULL;

    while(root) {
        ans.push_back(root);
        while(root) {
            if (root->left) {
                cur->sibling = root->left;
                cur = cur->sibling;
            }
            if (root->right) {
                cur->sibling = root->right;
                cur = cur->sibling;
            }
            root = root->sibling;
        }
        cur->sibling = NULL;
        root = dummy.sibling;
        cur = &dummy;
   }
   return ans;
}

//method 2
vector<Tree *> genSibling2(Tree *root)
{
    queue<Tree *> queue1, queue2;
    queue<Tree *> *myQue1, *myQue2;
    vector<Tree *> ans;
    
    myQue1 = &queue1;
    myQue2 = &queue2;
    myQue1->push(root);
    while(!myQue1->empty()) {
        ans.push_back(myQue1->front());
        while (!myQue1->empty()) {
            Tree *cur = myQue1->front();
            myQue1->pop();
            if (!myQue1->empty()) cur->sibling = myQue1->front();
            else cur->sibling = NULL;
            if (cur->left) myQue2->push(cur->left);
            if (cur->right) myQue2->push(cur->right);
        }
        queue<Tree *> *tmp = myQue1;
        myQue1 = myQue2;
        myQue2 = tmp; 
    }
    return ans;
}

//method 2
vector<Tree *> genSibling3(Tree *root)
{
    vector<Tree *> ans;
    queue<Tree *> myQue;
    if (!root) return ans;
    int curLevel = 1, nextLevel = 0;
    myQue.push(root);
    bool head = true;
    
    while(!myQue.empty()) {
        if (head) {
            ans.push_back(myQue.front());
            head = false;
        }
        Tree *tmp = myQue.front();
        myQue.pop();
        if (!myQue.empty()) tmp->sibling = myQue.front();
        curLevel--;
        if (tmp->left) {
            myQue.push(tmp->left);
            nextLevel++;
        }
        if (tmp->right){
            myQue.push(tmp->right);
            nextLevel++;
        }
        if (curLevel == 0) {
            tmp->sibling = NULL;
            head = true;
            curLevel = nextLevel;
            nextLevel = 0;
        }
    }
    return ans;
}


vector<Tree *> genSibling4(Tree *root)
{
    cout << "Sibling4" << endl;
    Tree *dummy = new Tree(0);
    Tree *cur = dummy;
    vector<Tree *> ans;
    root->sibling = NULL;
    ans.push_back(root);
    while(root) {
        if (root->left) {
             cur->sibling = root->left;
             cur = cur->sibling;
        } 
        if (root->right) {
            cur->sibling = root->right;
            cur = cur->sibling;
        }
        if (!root->sibling) {
            cur->sibling = NULL;
            root = dummy->sibling;
            ans.push_back(root);
	    cur = dummy;
        } else {
            root = root->sibling;
        }
    }

    free(dummy);
    return ans;
}

int main(int argc, char **argv)
{
    int input[] = {7,5,6,3,2,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    vector<Tree *> result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    print_ascii_tree(root);

    result = genSibling4(root);
    for (int i = 0; i < result.size(); i++) {
        Tree *head = result[i];
        while(head!= NULL) {
            cout << head->data << " ";
            head = head->sibling;
        }
        cout << endl;
    }
}
